A directory server is a special purpose database, which stores a set of information with identical or similar attributes organized in a hierarchical manner. A directory database is always used in applications, such as naming service, user registry, White Page lookup and so forth. For example, the telephone directory database consists of a series of names (either of people names or organization names) organized alphabetically, each name item has attributes such as address, phone number and others.
Since the directory database is designed as read-oriented, it always has relatively high throughput and relatively low latency in search operation workload. In order to improve the performance of search operation of the directory database, various techniques have been developed. However, the modifying or the modifying operation of entry names for the directory database has relatively slower performance than the search operation of the directory database. Although most of operations for the directory database are search operations, the ratio of modifying operations of entry names for the directory database is still as high as 20% in some applications (such as DNS routing, user authentication, telecommunication user management systems and so forth).
In conventional directory server, the latency of modifying operation of entry names is about several ten times higher than that of search operation, and the throughput drops significantly due to poor performance of modifying operation of entry names. Therefore, although the ratio of performing modifying operations of entry names in a directory server are relatively low, the performance of modifying operations has a huge negative influence on the performance of the server.
A lightweight directory access protocol (LDAP) is a protocol used to access online directory services. In the LDAP/X.500 specification are defined the following operations:                Search: {BaseDN, Scope, Filter, Attributes}        ModRDN: {Entry, NewRDN, DelOldRDN, NewSuperior}        Add/Delete/Update Attributes        
Where ModRDN (Modify DN) operation includes RDN rename operation and migrate operation. For more information about the LDAP/X.500 specification, please refer to RFC 2251 entitled “Lightweight Directory Access Protocol (v3)” and defined by the Internet Engineering Task Force (IETF), which is hereby incorporated by reference in its entirety.
LDAP directory can be implemented using various storage mechanisms, such as flat files, b-tree package and relational database. Most of them utilize designs, such as distinguished name to identifier, identifier to entry and attributes/indices, to transfer a hierarchical data model to a relational-like data model. Due to these designs, the modify operation becomes extraordinarily slow, which especially suffers during the modification to the distinguished name of a directory entry (ModRDN)
TABLE 1-1DN2ID(current node) DN->ID(child nodes) DN->ID list (IDL)(subtree nodes)DN-> ID list (IDL)
TABLE 1-2INDEXvalueIDL
TABLE 1-3ID2ENTRYIDENTRY
Tables 1-1, 1-2, 1-3 schematically show an implementation manner of OpenLDAP BDB. In the implementation of OpenLDAP BDB designed using DN2ID, Search operation only needs to perform one DB Read in the DN2ID table. During a ModRDN operation, n DB Writes need to be performed on the DN2ID table and the ID2ENTRY table for a subtree rename operation; and p+q+n DB Writes need to be performed on the DN2ID table and n DB Writes need to be performed on the ID2ENTRY table for a subtree migration operation, wherein n stands for the number of subtree entries affected, and p and q stand for the number of ancestor entries before and after migration respectively.
TABLE 2-1RDN2IDRDNParent
TABLE 2-2INDEXValueIDL
TABLE 2-3ID2ENTRYIDENTRY
Tables 2-1, 2-2, 2-3 schematically show an implementation manner of OpenLDAP HDB. In the implementation of OpenLDAP HDB, performance of ModRDN operation is improved. As a result, only one DB Write needs to be performed on the RDN2ID table and n DB Writes need to be performed on the ID2ENTRY table for a subtree Rename operation; and only one DB Write needs to performed on RDN2ID and n DB Writes need to be performed on the ID2ENTRY table for a subtree migration operation. However, such a design that is advantageous to modify entry name operation degrades the performance of Search operation dramatically, the DN2ID table of reference DN needs to be located with O(log2N) complexity, and expensive recursive search for subtree ID lists has to be done.
Apparently, in a conventional directory server, the performance of modify entry name operation is far worse than that of search operation, the relatively low operating efficiency and the relatively poor performance of modify entry name operation will greatly affect the operating efficiency and running performance of the whole directory server. In the implementation of OpenLDAP with the improvement of modify entry name operation, the performance of search operation will be impaired significantly, thereby being unable to achieve satisfying operating efficiency and run time performance of the directory server.